package SortAlgorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 题目 ：合并区间
 * 题目详述 ：
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
 * 请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
 */
public class Merge {
    /**
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        // 对于目标二维数组，根据区间的开始位置（即，intervals数组中各个数组元素[0]），从小到大进行排序；
        Arrays.sort(intervals , (p1 , p2) -> p1[0] - p2[0]);

        List<int[]> list = new ArrayList<>();
        // 用来标记正在遍历的区间在intervals数组中的下标
        // 若是区间合并的话，则i指向未进行合并操作的第一个区间
        int i = 0 ;
        // 对于排序后的数组intervals数组，进行区间合并操作；
        while(i < intervals.length){
            // 即，使用temp数组来保存第一个区间范围（开始位置，结束位置）
            int[] temp = new int[]{intervals[i][0] , intervals[i][1]};
            int j = i + 1; // 获取temp数组所存储区间的后一个区间next
            // 即，temp数组所存储区间的后一个区间next存在的话，同时满足temp区间的结束位置 >= next区间的开始位置的话，
            // ===》 将temp区间和next区间进行合并（merge）,
            /**
             *  为何需要使用while循环来进行区间合并操作？
             *  原因 ：
             *  （1）由于intervals数组是已经排序过的数组，所以每个区间的开始位置必然是递增的，
             *      排序好的数组能够确保temp区间合并结束之后，不存在有其他区间还能够合并到temp区间
             *  （2）若是当前遍历的区间temp能够将后面区间next进行合并的话，那么就会和后面的每一个区间进行比较，
             *  若是符合合并条件的话，会将后面区间next合并到temp区间中；
             *  但是若是不符合合并条件的话，则说明该temp区间已经不存在其他区间能够合并到此temp区间中；
             */
            while(j < intervals.length && temp[1] >= intervals[j][0]){
                // 即，获取temp区间和next区间中结束位置较大的那个值；
                temp[1] = Math.max(intervals[j][1] , temp[1]);
                // (1)temp区间将会去尝试合并再后面一个区间next；
                // (2)若是合并失败的话，则所有剩余区间中则不存在能够再合并到temp区间的区间；
                // (3)若是合并成功的话，则需要将j++，来去查询所有剩余区间中是否还存在能够合并到temp区间的区间；
                // （由于区间是根据开始位置来进行排序的，即intervals数组中所存储的区间是以开始位置顺序递增的）
                // （4）重复以上步骤；
                j++;
            }
            list.add(temp);
            i = j;
        }
        // 构建和list集合大小一样的二维数组；（用来存储list集合中所记录下的合并区间）
        int[][] result = new int[list.size()][];
        // 调用list.toArry方法，将list集合中的元素，存储到array数组中；
        return list.toArray(result);
    }
    /**
     * 分析 ：
     * （1）对于intervals数组进行排序，若是intervals数组中有n个元素的话，那么所花费的时间复杂度:O（nlogn）；
     * （2）对于排序好的intervals数组扫描，同时进行区间合并操作，由于每个intervals中所保存的数组都只会被扫描一次，所以时间复杂度O（n）；
     */
}
